package com.zgkxzx.数据结构.树.二叉树;

/**
 * 创建者 zgkxzx
 * 日期   12/21/17
 * 描述
 */

public class BinaryTree<T extends BaseNodeData> {
    public static final int MIN = Integer.MIN_VALUE;
    public Node<T> root;

    public BinaryTree(Node<T> root) {
        this.root = root;
    }

    /**
     * 添加节点
     *
     * @param node
     */
    public void insertNode(Node<T> node) {
        if (root == null)
            this.root = node;
        else {
            Node currentNode = root;
            while (currentNode != null) {
                if (node.data.compareTo(currentNode.data) > 0) {
                    if (currentNode.rightNode == null) {
                        currentNode.rightNode = node;
                        return;
                    }
                    currentNode = currentNode.rightNode;
                } else {
                    if (currentNode.leftNode == null) {
                        currentNode.leftNode = node;
                        return;
                    }
                    currentNode = currentNode.leftNode;
                }
            }
        }
    }

    /**
     * 得到二叉树的深度
     *
     * @param node
     * @return
     */
    public static int getTreeDeep(Node node) {
        if (node == null)
            return 0;
        int leftDegree = getTreeDeep(node.leftNode);
        int rightDegree = getTreeDeep(node.rightNode);
        int maxDegree = leftDegree > rightDegree ? leftDegree : rightDegree;
        return maxDegree + 1;
    }

    /**
     * 获取最大值的节点
     *
     * @param node
     * @param <T>
     * @return
     */
    public static <T extends BaseNodeData> Node<T> getMaxValue(Node<T> node) {
        if (node == null)
            return null;
        else {
            Node<T> leftNode = getMaxValue(node.leftNode);
            Node<T> rightNode = getMaxValue(node.rightNode);
            Node<T> maxNode = node;
            if (leftNode != null && leftNode.data.compareTo(maxNode.data) > 0) {
                maxNode = leftNode;
            }
            if (rightNode != null && rightNode.data.compareTo(maxNode.data) > 0) {
                maxNode = rightNode;
            }
            return maxNode;
        }
    }

    /**
     * 删除
     * @param node
     */
    public void deleteNode(Node node) {
        if(node==null)
            return;
        Node searchNode = searchNode(node);
        delete(searchNode);
    }

    private void delete(Node searchNode) {


    }

    /**
     * 查找
     * @param node
     * @return
     */
    public Node<T> searchNode(Node<T> node) {
        if (node == null)
            return null;
        else {
            Node temp = root;
            while (temp != null) {
                if (node.data.compareTo(temp.data) > 0) {
                    temp = temp.rightNode;
                } else if (node.data.compareTo(temp.data) < 0) {
                    temp = temp.leftNode;
                } else {
                    return temp;
                }

            }
            return temp;
        }

    }

    public static <T extends BaseNodeData> Node<T> searchNode(Node<T> root, Node<T> node) {
        if (node == null)
            return null;

        if (root != null) {
            if (root.data.isSearchSample(node.data)) {
                return root;
            }
            Node<T> leftNode = searchNode(root.leftNode, node);

            if (leftNode != null && leftNode.data.isSearchSample(node.data)) {
                return leftNode;
            }

            Node<T> rightNode = searchNode(root.rightNode, node);
            if (rightNode != null && rightNode.data.isSearchSample(node.data)) {
                return rightNode;
            }
        }

        return null;
    }

    /**
     * 得到的叶子数
     *
     * @param node
     * @param count
     * @return
     */
    public static int getLeafCount(Node node, int count) {
        if (node == null)
            return count;
        if (node.leftNode == null && node.rightNode == null)
            count++;
        count = getLeafCount(node.leftNode, count);
        count = getLeafCount(node.rightNode, count);
        return count;
    }


    public static <T extends BaseNodeData> Node<T> getMaxValue2(Node<T> node) {
        if (node == null)
            return null;
        else {
            //TODO 这里注意引用问题 是否改变形参
            while (node.rightNode != null) {
                node = node.rightNode;
            }
            return node;
        }
    }

    /**
     * 先序遍历
     *
     * @param node
     */
    public static void preOrderTraverse(Node node) {
        if (node == null)
            return;
        System.out.println("Node -> " + node.data);
        preOrderTraverse(node.leftNode);
        preOrderTraverse(node.rightNode);
    }

    /**
     * 后序遍历
     *
     * @param node
     */
    public static void postOrderTraverse(Node node) {
        if (node == null)
            return;

        postOrderTraverse(node.leftNode);
        postOrderTraverse(node.rightNode);
        System.out.println("Node -> " + node.data);
    }

    /**
     * 中序遍历
     *
     * @param node
     */
    public static void inOrderTraverse(Node node) {
        if (node == null)
            return;

        inOrderTraverse(node.leftNode);
        System.out.println("Node -> " + node.data);
        inOrderTraverse(node.rightNode);
    }


    /**
     * 节点实体类
     * @param <T>
     */
    public static class Node<T extends BaseNodeData> {
        public T data;
        public Node<T> leftNode;
        public Node<T> rightNode;

        public Node(T data) {
            this.data = data;
        }

    }


}
